import java.util.ArrayList;
import java.util.List;

public class BinaryTree<T> {
    BinaryNode<T> root;
    public BinaryTree(){
        this.root = null;
    }
    public boolean isEmpty(){
        return this.root == null;
    }
    public void insert(T x){
        if(x != null){
            this.root = new BinaryNode<>(x, this.root, null);
        }
    }
    public void preorder(BinaryNode<T> root){
        if(root == null){
            System.out.print(" null");
            return;
        }
        System.out.print(" " + root.val);
        preorder(root.left);
        preorder(root.right);
    }
    public BinaryTree(T[] prelist){
        this.root = create(prelist);
    }
    private int i = 0;
    private BinaryNode<T> create(T[] prelist){
        BinaryNode<T> p = null;
        if(i < prelist.length){
            T elem = prelist[i++];
            if(elem != null){
                p = new BinaryNode<T>(elem);
                p.left = create(prelist);
                p.right = create(prelist);
            }
        }
        return p;
    }
    public List<BinaryNode<T>> search1(BinaryTree<T> pattern){
        List<BinaryNode<T>> res = new ArrayList<>();
        List<BinaryNode<T>> find = search(root,pattern.root.val);
        for(BinaryNode<T> x : find){
            if(isSame(x, pattern.root)){
                res.add(x);
            }
        }
        return res;
    }
    public BinaryNode<T> preorderFind(BinaryNode<T> root, BinaryNode<T> x){
        if(root == null) return null;
        if(root.left == x || root.right == x){
            return node = root;
        }
        if(root != null && (preorderFind(root.left, x)!=null || preorderFind(root.right, x)!=null)){
            return node;
        }
        return null;
    }
    BinaryNode<T> node = null;
    public void deleteSearch(BinaryTree<T> pattern){
        List<BinaryNode<T>> find = search1(pattern);
        for (BinaryNode<T> x : find) {
            node = null;
            node = preorderFind(this.root,x);
            if(node != null && node.left == x) node.left = null;
            if(node != null && node.right == x) node.right = null;
        }
    }
    public BinaryNode<T> search(BinaryTree<T> pattern){
        List<BinaryNode<T>> find = search(root,pattern.root.val);
        for(BinaryNode<T> x : find){
            if(isSame(x, pattern.root)){
                return x;
            }
        }
        return null;
    }
    public List<BinaryNode<T>> search(BinaryNode<T> root, T val){
        List<BinaryNode<T>> t = new ArrayList<>();
        if(root == null) return t;
        if(root.val == val) t.add(root);
        List<BinaryNode<T>> left = search(root.left,val);
        List<BinaryNode<T>> right = search(root.right,val);
        t.addAll(left);
        t.addAll(right);
        return t;
    }
    public boolean isSame(BinaryNode<T> a, BinaryNode<T> b){
        if(a == null || b == null) return a == b;
        return a.val == b.val &&
                isSame(a.left,b.left) &&
                isSame(a.right, b.right);
    }

    public static void main(String[] args) {

        String[] s = {"A","B","D",null,"F",null,null,"C","E",null,null,"J","H"};
        String[] s1 = {"J","H"};
        BinaryTree<String> tree1 = new BinaryTree<>(s1);
        BinaryTree<String> tree = new BinaryTree<>(s);
        System.out.println("初始值: ");
        tree.preorder(tree.root);
        System.out.println();
        System.out.println("pattern: ");
        tree1.preorder(tree1.root);
        tree.deleteSearch(tree1);
        System.out.println();
        System.out.println("删除子树后: ");
        tree.preorder(tree.root);

    }
}
